package class12;

import java.util.Arrays;
import java.util.HashMap;

/**
 *
 * 给定一个字符串str,给定一个字符串类型的数组arr
 * arr里的每一个字符串,代表一张贴纸,你可以把单个字符剪开使用,目的是拼出str来
 * 返回需要至少多少张贴纸可以完成这个任务
 *
 * 例子: str="babac", arr={"ba","c","abcd"}
 * 至少需要两张贴纸"ba"和"abcd",因为可以使用这两张贴纸,把每一个字符单独剪开,含有2个a,2个b,1个c
 * 是可以拼出str的,所以返回2
 *
 *
 * 如何找到某个问题的动态规划方式:
 * 1.设计暴力递归: 重要原则(重复过程,可变参数少)+4种常见尝试模型
 * 2.分析有没有重复解: 套路解决
 * 3.记忆化搜索 -> 用严格表结构实现动态规划: 套路解决
 * 4.看看能否继续优化: 套路解决
 *
 * 暴力递归过程的原则
 * 1.每一个可变参数的类型,一定不要比int类型更加复杂
 * 2.原则1)可以违反,让类型突破到一维线性结构,那必须是唯一可变参数
 * 3.如果发现原则1)被违反,但不违反原则2),只需要做到记忆化搜索即可
 * 4.可变参数的个数,能少则少
 *
 * 常见的尝试模型
 * 1.从左往右的阐释模型
 * 2.范围上的尝试模型
 * 3.多样本位置全对应的尝试模型
 * 4.寻找业务限制的尝试模型
 *
 * 暴力递归到动态规划的套路
 * 1.你已经有了一个不违反原则的暴力递归,而且的确存在解的重复调用
 * 2.找到哪些参数的变化会影响返回值,对每一个列出变化范围
 * 3.参数间的所有的组合数量,意味着表大小
 * 4.记忆化搜素的方法就是傻缓存,非常容易得到
 * 5.规定好严格表大小,分析位置的依赖顺序,然后从基础填写到最终解
 * 6.对于有枚举行为的决策过程,进一步优化
 *
 * 动态规划的进一步优化
 * 1.空间压缩
 * 2.状态化简
 * 3.四边形不等式
 * 4.其他优化技巧
 *
 */
public class Code02_StickersToSpellWord {


	//尝试方式一(更优,可变参数越少越好)
	public static int minStickers1(String[] stickers, String target) {
		
		int n = stickers.length;

		//a->0 b->1 进行下标映射
		//二维数值的值
		int[][] map = new int[n][26];// stickers -> [26] [26] [26]
		//i表示第几张词条,同行26个位置(0-25)表示该词条每个字符出现的次数
		for (int i = 0; i < n; i++) {
			char[] str = stickers[i].toCharArray();
			for (char c : str) {
				map[i][c - 'a']++;
			}
		}

		//剩余目标缓存
		HashMap<String, Integer> dp = new HashMap<>();
		dp.put("", 0);
		return process1(dp, map, target);
	}

	// dp 傻缓存，如果t已经算过了，直接返回dp中的值
	// t 剩余的目标
	// 0..N每一个字符串所含字符的词频统计
	// 返回值是-1，map 中的贴纸  怎么都无法rest
	public static int process1(
			HashMap<String, Integer> dp,
			int[][] map, 
			String rest) {
		if (dp.containsKey(rest)) {
			return dp.get(rest);
		}
		// 以下就是正式的递归调用过程
		int ans = Integer.MAX_VALUE; // ans -> 搞定rest，使用的最少的贴纸数量 
		int n = map.length; // N种贴纸
		int[] tmap = new int[26]; // tmap 去替代 rest
		char[] target = rest.toCharArray();
		for (char c : target) {
			tmap[c - 'a']++;
		}
		//先消除 a
		//再消除 b
		//...
		//最终消除 z
		for (int i = 0; i < n; i++) {
			// 枚举当前第一张贴纸是谁？
			// 即: 当前贴纸至少包含第rest中的第一个字符(按字典顺序排序的)
			// 或者当前贴纸至少包含rest中的其中一个字符
			if (map[i][target[0] - 'a'] == 0) {
				continue;
			}
			StringBuilder sb = new StringBuilder();
			// i 贴纸， j 枚举a~z字符
			for (int j = 0; j < 26; j++) { // 
				if (tmap[j] > 0) { // j这个字符是target需要的
					//减去词条后剩下的字符串是什么(单个字符最小为0,没必要考虑负数)
					for (int k = 0; k < Math.max(0, tmap[j] - map[i][j]); k++) {
						sb.append((char) ('a' + j));
					}
				}
			}
			// sb ->  i
			String s = sb.toString();
			int tmp = process1(dp, map, s);
			if (tmp != -1) {
				ans = Math.min(ans, 1 + tmp);
			}
		}
		// 缓存
		// ans 系统最大  rest
		dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
		return dp.get(rest);
	}


	//尝试方式二:(更暴力)
	//先尝试贴纸1, 使用了 1 张
	//再尝试贴纸1, 使用了 2 张
	//..
	//再尝试贴纸1, 使用了 n 张(N*字符数 < target)
	//再尝试贴纸2, 使用了 1 张
	//再尝试贴纸2, 使用了 2 张
	//...
	public static int minStickers2(String[] stickers, String target) {
		int n = stickers.length;
		int[][] map = new int[n][26];
		for (int i = 0; i < n; i++) {
			char[] str = stickers[i].toCharArray();
			for (char c : str) {
				map[i][c - 'a']++;
			}
		}
		char[] str = target.toCharArray();
		int[] tmap = new int[26];
		for (char c : str) {
			tmap[c - 'a']++;
		}
		HashMap<String, Integer> dp = new HashMap<>();
		int ans = process2(map, 0, tmap, dp);
		return ans;
	}

	public static int process2(int[][] map, int i, int[] tmap, HashMap<String, Integer> dp) {
		StringBuilder keyBuilder = new StringBuilder();
		keyBuilder.append(i + "_");
		for (int asc = 0; asc < 26; asc++) {
			if (tmap[asc] != 0) {
				keyBuilder.append((char) (asc + 'a') + "_" + tmap[asc] + "_");
			}
		}
		String key = keyBuilder.toString();
		if (dp.containsKey(key)) {
			return dp.get(key);
		}
		boolean finish = true;
		for (int asc = 0; asc < 26; asc++) {
			if (tmap[asc] != 0) {
				finish = false;
				break;
			}
		}
		if (finish) {
			dp.put(key, 0);
			return 0;
		}
		if (i == map.length) {
			dp.put(key, -1);
			return -1;
		}
		int maxZhang = 0;
		for (int asc = 0; asc < 26; asc++) {
			if (map[i][asc] != 0 && tmap[asc] != 0) {
				maxZhang = Math.max(maxZhang, (tmap[asc] / map[i][asc]) + (tmap[asc] % map[i][asc] == 0 ? 0 : 1));
			}
		}
		int[] backup = Arrays.copyOf(tmap, tmap.length);
		int min = Integer.MAX_VALUE;
		int next = process2(map, i + 1, tmap, dp);
		tmap = Arrays.copyOf(backup, backup.length);
		if (next != -1) {
			min = next;
		}
		for (int zhang = 1; zhang <= maxZhang; zhang++) {
			for (int asc = 0; asc < 26; asc++) {
				tmap[asc] = Math.max(0, tmap[asc] - (map[i][asc] * zhang));
			}
			next = process2(map, i + 1, tmap, dp);
			tmap = Arrays.copyOf(backup, backup.length);
			if (next != -1) {
				min = Math.min(min, zhang + next);
			}
		}
		int ans = min == Integer.MAX_VALUE ? -1 : min;
		dp.put(key, ans);
		return ans;
	}
	
	public static void main(String[] args) {
		String[] arr = {"aaaa","bbaa","ccddd"};
		String str = "abcccccdddddbbbaaaaa";
		System.out.println(minStickers1(arr, str));
		System.out.println(minStickers2(arr, str));
		
		
	}

}
